#include <iostream>
#include <vector>
using namespace std;
//堆排序
//向上调整算法
void upAdjust(vector<int>& v, int index)
{
	int child = index;
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (v[child] > v[parent]) {
			std::swap(v[child], v[parent]);
			//更新child和parent
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
	return;
}

void downAdjust(vector<int>& v, int index)
{
	int parent = 0;
	int child = 1;
	while (child <= index) {
		if (child + 1 <= index && v[child] < v[child+1]) {
			child = child + 1;
		}
		if (v[parent] < v[child]) {   //不一定交换后堆的根一定小于孩子节点，必须要有判断条件
			std::swap(v[parent], v[child]);
		}
		else {
			break;  //这个终止条件如果没有的话，整个过程也是正确的，这个终止条件节省了不必要的比较而已，也就是优化性能
		}
		parent = child;
		child = 2 * parent + 1;
	}
}

int main()
{
vector<int> v = { 3,5,1,9,0,3,1,2,8,7,4 };
	for (size_t i = 1;i < v.size();++i) {
		upAdjust(v, i); //构建一个大根堆
	}
	int end = v.size()-1;
	while (end > 0) {
	std::swap(v[0], v[end--]);
	downAdjust(v, end);
	}
	for (const auto& num : v) {
		cout << num << " ";
	}
	cout << endl;
    return 0;
}